package problem99_Recover_Binary_Search_Tree;

import problem95_UniqueBinarySearchTreesII.MySolution.TreeNode;

public class MySolution {
	private TreeNode pre=null,mistake1=null,mistake2=null;
	
	private void inorder(TreeNode root) {
		if(root!=null){
			inorder(root.left);
			if(pre!=null&&pre.val>=root.val){
				mistake1=(mistake1==null?pre:mistake1);
				mistake2=root;
			}
			pre=root;
			inorder(root.right);
		}
    }
	
	public void recoverTree(TreeNode root){
		inorder(root);
		if(mistake1!=null&&mistake2!=null){
			int tmp=mistake1.val;
			mistake1.val=mistake2.val;
			mistake2.val=tmp;
		}
	}
	
}
